#define _CRT_SECURE_NO_WARNINGS
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct binarytreenode {
	struct binarytreenode* left;
	struct binarytreenode* right;
	int val;
}BTNode;
#include"Queue.h"
BTNode* BuyNode(int x) {
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	node->val = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

void PrevOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

void InOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

int TreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		return TreeSize(root->right) + TreeSize(root->left) + 1;
	}
}

int TreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	return TreeLeafSize(root->right) + TreeLeafSize(root->left);
}

int TreeKSzie(BTNode* root, int k) {
	assert(k > 0);
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return TreeKSzie(root->left, k - 1) + TreeKSzie(root->right, k - 1);
 }

BTNode* TreeFind(BTNode* root, int x) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == x) {
		return root;
	}
	BTNode* ret = TreeFind(root->left, x);
	if (ret != NULL) {
		return ret;
	}
	return TreeFind(root->right, x);
}

void LevelOrder(BTNode* root) {
	Que q;
	QueueInit(&q);
	if(root)
	QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		BTNode* tmp = QueueFront(&q);
		printf("%d ", tmp->val);
		if (QueueFront(&q)->left) {
			QueuePush(&q,tmp->left);
		}
		if (QueueFront(&q)->right) {
			QueuePush(&q,tmp->right);
		}
		QueuePop(&q);
	}
	QueueDestroy(&q);
}
int TreeHeight(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return (int)fmax(TreeHeight(root->left), TreeHeight(root->right))+1;
	//int h1 = TreeHeight(root->left);
	//int h2 = TreeHeight(root->right);
	//if (h1 > h2) {
	//	return h1+1;
	//}
	//else {
	//	return h2+1;
	//}
}

bool TreeComplete(BTNode* root) {
	Que q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q,root);
	}
	while (QueueFront(&q) != NULL) {
		BTNode* tmp = QueueFront(&q);
			QueuePush(&q, tmp->left);
			QueuePush(&q, tmp->right);
		QueuePop(&q);
	}
	while (!QueueEmpty(&q)) {
		if (QueueFront(&q) != NULL) {
			QueueDestroy(&q);
			return false;
		}
		QueuePop(&q);
	}
	//QNode* cur = q.head;
	//while (cur) {
	//	if (cur->data != NULL) {
	//		QueueDestroy(&q);
	//		return false;
	//	}
	//	cur = cur->next;
	//}
	QueueDestroy(&q);
	return true;
}


int main() {
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	node2->right = node5;
	node4->left = node6;
	printf("TreeSize=%d\n", TreeSize(node1));
	printf("TreeLeafSize=%d\n", TreeLeafSize(node1));
	printf("TreeKSzie=%d\n", TreeKSzie(node1, 3));
	printf("TreeFind4=%d\n", (TreeFind(node1, 4))->val);
	LevelOrder(node1);
	printf("\n%d\n", TreeHeight(node1));
	int ret=TreeComplete(node1);
	printf("%d", ret);
	return 0;
}